Press "Enter" to skip to content

深入理解PHP之数组(遍历顺序)

Published on 23 August 2009 by laruence

经常会有人问我, PHP的数组, 如果用foreach来访问, 遍历的顺序是固定的么? 以什么顺序遍历呢?
比如:

<?php
$arr['laruence'] = 'huixinchen';
$arr['yahoo']    = 2007;
$arr['baidu']    = 2008;
foreach ($arr as $key => $val) {
//结果是什么?
}

又比如:

<?php
$arr[2] = 'huixinchen';
$arr[1]  = 2007;
$arr[0]  = 2008;
foreach ($arr as $key => $val) {
//现在结果又是什么?
}

要完全了解清楚这个问题, 我想首先应该要大家了解PHP数组的内部实现结构.........

PHP的数组

在PHP中, 数组是用一种HASH结构(HashTable)来实现的, PHP使用了一些机制, 使得可以在O(1)的时间复杂度下实现数组的增删, 并同时支持线性遍历和随机访问.
之前的文章中也讨论过, PHP的HASH算法, 基于此, 我们做进一步的延伸.
认识HashTable之前, 首先让我们看看HashTable的结构定义, 我加了注释方便大家理解:

typedef struct _hashtable {
uint nTableSize;        /* 散列表大小, Hash值的区间 */
uint nTableMask;        /* 等于nTableSize -1, 用于快速定位 */
uint nNumOfElements;    /* HashTable中实际元素的个数 */
ulong nNextFreeElement; /* 下个空闲可用位置的数字索引 */
Bucket *pInternalPointer;   /* 内部位置指针, 会被reset, current这些遍历函数使用 */
Bucket *pListHead;      /* 头元素, 用于线性遍历 */
Bucket *pListTail;      /* 尾元素, 用于线性遍历 */
Bucket **arBuckets;     /* 实际的存储容器 */
dtor_func_t pDestructor;/* 元素的析构函数(指针) */
zend_bool persistent;
unsigned char nApplyCount; /* 循环遍历保护 */
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

关于nApplyCount的意义, 我们可以通过一个例子来了解:

<?php
    $arr = array(1,2,3,4,5,);
    $arr[] = &$arr;
    var_export($arr); //Fatal error: Nesting level too deep - recursive dependency?

这个字段就是为了防治循环引用导致的无限循环而设立的.
查看上面的结构, 可以看出, 对于HashTable, 关键元素就是arBuckets了, 这个是实际存储的容器, 让我们来看看它的结构定义:

typedef struct bucket {
ulong h;                        /* 数字索引/hash值 */
uint nKeyLength;                /* 字符索引的长度 */
void *pData;                    /* 数据 */
void *pDataPtr;                 /* 数据指针 */
struct bucket *pListNext;               /* 下一个元素, 用于线性遍历 */
struct bucket *pListLast;       /* 上一个元素, 用于线性遍历 */
struct bucket *pNext;                   /* 处于同一个拉链中的下一个元素 */
struct bucket *pLast;                   /* 处于同一拉链中的上一个元素 */
char arKey[1]; /* 节省内存,方便初始化的技巧 */
} Bucket;

我们注意到, 最后一个元素, 这个是flexible array技巧, 可以节省内存,和方便初始化的一种做法, 有兴趣的朋友可以google flexible array.
h是元素的Hash值,对于数字索引的元素,h为直接索引值(通过nKeyLength=0来表示是数字索引).而对于字符串索引来说, 索引值保存在arKey中, 索引的长度保存在nKeyLength中.
在Bucket中，实际的数据是保存在pData指针指向的内存块中，通常这个内存块是系统另外分配的。但有一种情况例外，就是当Bucket保存 的数据是一个指针时，HashTable将不会另外请求系统分配空间来保存这个指针，而是直接将该指针保存到pDataPtr中，然后再将pData指向本结构成员的地址。这样可以提高效率，减少内存碎片。由此我们可以看到PHP HashTable设计的精妙之处。如果Bucket中的数据不是一个指针，pDataPtr为NULL(本段来自Altair的"Zend HashTable详解")
结合上面的HashTable结构, 我们来说明下HashTable的总结构图:

HashTable结构示意图
HashTable结构示意图

HashTable的pListhHead指向线性列表形式下的第一个元素, 上图中是元素1, pListTail指向的是最后一个元素0, 而对于每一个元素pListNext就是红色线条画出的线性结构的下一个元素, 而pListLast是上一个元素.
pInternalPointer指向当前的内部指针的位置, 在对数组进行顺序遍历的时候, 这个指针指明了当前的元素.
当在线性(顺序)遍历的时候, 就会从pListHead开始, 顺着Bucket中的pListNext/pListLast, 根据移动pInternalPointer, 来实现对所有元素的线性遍历.
比如, 对于foreach, 如果我们查看它生成的opcode序列, 我们可以发现, 在foreach之前, 会首先有个FE_RESET来重置数组的内部指针, 也就是pInternalPointer(关于foreach可以参看深入理解PHP原理之foreach), 然后通过每次FE_FETCH来递增pInternalPointer,从而实现顺序遍历.
类似的, 当我们使用, each/next系列函数来遍历的时候, 也是通过移动数组的内部指针而实现了顺序遍历, 这里有一个问题, 比如:

<?php
$arr = array(1,2,3,4,5);
foreach ($arr as $v) {
//可以获取
}
while (list($key, $v) = each($arr)) {
//获取不到
}
?>

了解到我刚才介绍的知识, 那么这个问题也就很明朗了, 因为foreach会自动reset, 而while这块不会reset, 所以在foreach结束以后, pInternalPointer指向数组最末端, while语句块当然访问不到了, 解决的办法就是在each之前, 先reset数组的内部指针.
而在随机访问的时候, 就会通过hash值确定在hash数组中的头指针位置, 然后通过pNext/pLast来找到特点元素.
增加元素的时候, 元素会插在相同Hash元素链的头部和线性列表的尾部. 也就是说, 元素在线性遍历的时候是根据插入的先后顺序来遍历的, 这个特殊的设计使得在PHP中,当使用数字索引时, 元素的先后顺序是由添加的顺序决定的,而不是索引顺序.
也就是说, PHP中遍历数组的顺序, 是和元素的添加先后相关的, 那么, 现在我们就很清楚的知道, 文章开头的问题的输出是:

huixinchen
2007
2008

所以, 如果你想在数字索引的数组中按照索引大小遍历, 那么你就应该使用for, 而不是foreach

for($i=0,$l=count($arr); $i<$l; $i++) {
 //这个时候,不能认为是顺序遍历(线性遍历)
}

Filed in PHP应用, PHP源码分析

42 Comments

  3. Salamander
    Salamander October 11, 2019

    什么时候拉链部分可以换成红黑树呢，Java 8的HashMap已经做了

  4. unset后的PHP内存管理 - 歪麦博客
    unset后的PHP内存管理 - 歪麦博客 June 10, 2019

    […] 可以参看我之前的文章深入理解PHP之数组(遍历顺序)), 数组也是用她来表示的, 而符号表也是一种关联数组, […]

  6. jiayuan
    jiayuan March 2, 2017

    有个问题想问下，当数组很大时，比如100万，要在其中查询一个值是否存在，in_array需要的时间比较久，当用array_flip键值互换，再用isset则会快很多，不太明白原因，arBuckets中“h是元素的Hash值”“索引值保存在arKey中”，我的感觉是in_array是根据h来判断元素是否存在，isset使用arKey来判断，这两个并没有实质性的差别，为啥时间会差很多呢？可能我的理解方式不对，希望能得到解答，谢谢~~~

  7. peanut
    peanut January 3, 2016

    想查看鸟哥的深入理解php系列，要是能有个目录的话，感激不尽。。

  8. Mithaftungen
    Mithaftungen December 6, 2015

    &#5034ѵoіɗ Ѕtаffіng Ɗі&#8572еmmаѕ:
    &#5025ecօցniz&#6513 Wɦеn &#5036mρl&#11423уееs
    Αгe Unhɑρρу
    &#8544f у&#1086&#6489 сɑtϲɦ
    ɑny &#1086f yo&#6489r &#6513m&#11427lοуeеѕ plaуіng
    thе caг&#8574 ցɑmе Cօгρоrаtе СҺаоѕ (үeѕ, it’ѕ
    геɑl) in t&#1211е cafetегіа, ʏߋս mɑү Ье t&#1086o lɑte.
    &#11406ееге iѕ mү ѡeb&#8572&#1086ց – Mithaftungen

  9. Desmond
    Desmond June 12, 2015

    您好，请原谅无知的我再次刷屏：
    经过几次测试，我想跟您确认下，是不是如果将一个数组赋值给另一个变量后，该数组会使用reset()调整自身的指针，重新指向第一个位置？
    希望能看到您关于《深入理解PHP之数组(赋值)》的内容。

  10. Desmond
    Desmond June 12, 2015

    您好，非常抱歉，请忽略我的这三条评论：
    当我在current($array)前使用reset()后又正常了！（明明记得昨天还不正常的）
    正如文章中说的，使用foreach遍历过数组后，需要reset()将指针重定向到第一个位置，方可使用current()得到数组中的第一个值

  11. Desmond
    Desmond June 12, 2015

    您好，我刚刚又可以重现上条留言中提到的现象了：当将数组A又赋值给另一个新变量B时，使用current()可以取得该数组A的当前值了，否则为false。
    以下代码是涉及到问题的代码，请赐教。
    //uni_accounts()返回一个多维数组
    $accounts = uni_accounts();//使用current()无法获取当前值（第一个值）
    //$_accounts = $accounts = uni_accounts();//使用current()可以获取当前值（第一个值）
    print_r($accounts);
    print_r(current($accounts));
    exit;

  12. Desmond
    Desmond June 12, 2015

    您好，想请教个问题：
    什么样的一个数组会出现使用print_r()可以打印出它的内容，但使用current()获取不到它的当前值（也是第一个值，即使在current()前使用了reset() ，结果依然是false），但使用array_shift却可以？
    （昨天在写某段代码时遇到的这个现象，百思不得解，今天读了您这文章后，想再研究下，发现又可以通过current()获得值了，所以更奇怪了）
    希望您能帮我一下，谢谢！

  14. php中的HashTable实现 | 种花生的黄土地
    php中的HashTable实现 | 种花生的黄土地 November 16, 2013

    […] 两个双向的链表：第一个双向链表是数组的每个元素（桶bucket）是一个双向链表，这样做是为了解决hash冲突；第二个双向链表是数组将每一个桶(bucket)连接起来，这里要连接的也就是第一个双向链表的链表头，这样做是为了遍历整个hash表用的,鸟哥有篇blog是讲php的foreach的，这里这样设计就是给foreach用的==>《深入理解PHP之数组(遍历顺序)》 […]

  15. stauren
    stauren July 25, 2013

    大牛，一搜php的底层实现又见你……

  16. Zjmainstay
    Zjmainstay July 16, 2013

    “增加元素的时候, 元素会插在相同Hash元素链的头部和线性列表的尾部. 也就是说, 元素在线性遍历的时候是根据插入的先后顺序来遍历的, 这个特殊的设计使得在PHP中,当使用数字索引时, 元素的先后顺序是由添加的顺序决定的,而不是索引顺序.”
    这里提到“相同Hash元素链的头部”和“线性列表的尾部”，这里不是太明白，还望楼主讲解一下。

  17. 巫旭东
    巫旭东 May 7, 2013

    很好奇pData指向的那块内存是怎么分配的，对于不定长数据的话，怎么做到碎片最小

  21. alex
    alex August 9, 2011

    喜欢这种底层分析的文章，期待更多分享啊。

  23. php 内存管理 | 到此一游
    php 内存管理 | 到此一游 June 23, 2011

    […] 可以参看我之前的文章深入理解PHP之数组(遍历顺序)), 数组也是用她来表示的, 而符号表也是一种关联数组, […]

  26. SPL学习笔记
    SPL学习笔记 October 7, 2010

    […] php程序员使用最多的数据结构应该就是数组(array)了吧，不管是实现个列表、队列、哈希还是别的什么数据集，都会先想到用array模拟，因为它既方便使用又功能强大(很多函数支持)。你甚至会不由得感叹，php的array真是万能啊！(php中array的底层实现方式可以参考深入理解PHP之数组) […]

  28. 雪候鸟
    雪候鸟 March 1, 2010

    @liruqi 呵呵, 还真是,,写错了, 谢谢

  29. liruqi
    liruqi March 1, 2010

    有个笔误.
    “对于数字索引来说, 索引值保存在arKey中, 索引的长度保存在nKeyLength中.”
    应该是”对于字符串索引”吧!

  30. PHP源码阅读笔记四：count函数 | 胖子的空间
    PHP源码阅读笔记四：count函数 | 胖子的空间 January 17, 2010

    […] 如果想直接运行HashTable的一些简单操作，猛击PHP源码中HashTable的简单示例 如果想查看了解数组存储或遍历的方式，猛击鸟哥的深入理解PHP之数组(遍历顺序) […]

  31. laja
    laja November 25, 2009

    array的count是直接取 nNumOfElements 吗？
    还是内部遍历？

  32. laruence
    laruence October 27, 2009

    pNext是同一hash值冲突时候拉链的下一个元素.
    pListNext是所有的元素的串联, 文章中有描述, 你可以再自习看看

  33. noname
    noname October 27, 2009

    博主您好
    请问一下，
    struct bucket *pNext;
    struct bucket *pLast;
    这两个指针的作用是什么，它们和
    struct bucket *pListNext;
    struct bucket *pListLast;
    的区别是什么
    谢谢

  34. jindw
    jindw October 16, 2009

    这可是个陷阱，看来火麒麟中间代码翻译那块该修改修改了。
    专业，受教。

  35. ning
    ning August 28, 2009

    所以, 如果你想在数字索引的数组中按照索引大小遍历, 那么你就应该使用for, 而不是foreach
    ksoft

  36. MaJia
    MaJia August 27, 2009

    楼主,好图啊!

  37. cyj
    cyj August 24, 2009

    已发送，请查收。

  38. 雪候鸟
    雪候鸟 August 23, 2009

    @cyj 如果可以的话, 请发送你的代码(全部可编译的)到我的邮箱, yahoo.com.cn的, 我帮你看看~

  39. 雪候鸟
    雪候鸟 August 23, 2009

    @膘叔 你的代码不全, 没看太明白, 但应该是内部指针的问题, 你可以在while之前reset一下, 看看是否正确.

  40. 膘叔
    膘叔 August 23, 2009

    $val) {
    //现在结果又是什么?
    echo( $val );
    echo( ” );
    }
    while (list($k, $value) = each($arr)) {
    echo “Key: $k; Value: $value\n”;
    }
    很奇怪，while那段是没有输出的。
    如果把这两个顺序填倒过来。则有输出
    如果在while结束后，输出字符，也是会有字符串输出，证明代码没有出错。
    何解？

  41. cyj
    cyj August 23, 2009

    博主您好，我现在遇到了一个问题。
    我定义了一个模块全局变量。
    ZEND_BEGIN_MODULE_GLOBALS(sample4)
    HASHTABLE *ht;
    ZEND_END_MODULE_GLOBALS(sample4)
    在
    101 static void php_hello1_init_globals(zend_hello1_globals *hello1_globals TSRMLS_DC)
    102 {
    103
    104 ALLOC_HASHTABLE(HELLO1_G(apps_config));
    105 if(zend_hash_init(HELLO1_G(apps_config),
    106 8, NULL, free_app_config, 0) == FAILURE)
    107 {
    108 FREE_HASHTABLE(HELLO1_G(apps_config));
    109 }
    110 char string[11] = “chenyujian”;
    111 zval *app_name ;
    112
    113 MAKE_STD_ZVAL(app_name);
    114 ZVAL_STRING(app_name, “chen”, 1);
    115
    116 if(zend_hash_add(HELLO1_G(apps_config), “bar”, sizeof(“bar”), &app_name, sizeof(zval*), NULL) == SUCCESS)
    117 {
    118 }
    119 if(zend_hash_add(HELLO1_G(apps_config), string, sizeof(string), &app_name, sizeof(zval*), NULL) == SUCCESS)
    120 {
    121 php_printf(“size of:%s:%d\n”,string,sizeof(string));
    122 }
    123 zval **args;
    124 if(zend_hash_find(HELLO1_G(apps_config), string, sizeof(string), (void **) &args) == SUCCESS)
    125 {
    126
    127 char *m = Z_STRVAL_PP(args);
    128 php_printf(“%s\n”,m);
    129 }else
    130 {
    131 php_printf(“not found”);
    132 }
    133 }
    134 static void php_hello1_globals_dtor(zend_hello1_globals *hello1_globals TSRMLS_DC)
    135 {
    136 zend_hash_destroy(HELLO1_G(apps_config));
    137 /* Free the HashTable itself */
    138 FREE_HASHTABLE(HELLO1_G(apps_config));
    139 HELLO1_G(apps_config) = NULL;
    140 }
    PHP_MINIT()里面进行HASH初始化，这时候遇到了几个问题，一，在Module中初始化后，在MSHUTDOWN中进行进行释放（
    136 zend_hash_destroy(HELLO1_G(apps_config));
    137 /* Free the HashTable itself */
    138 FREE_HASHTABLE(HELLO1_G(apps_config));）
    出现了segment fault错误。
    二：在rini中进行hashtable的hash_add出现了segmentfault错误。
    这让我百思不得其解，当然在rini中进行 hash_init 再进行 hash_add是没有问题的。不知道究竟是什么原因。

  42. phppan
    phppan August 23, 2009

    学习了！
    感谢LZ

Comments are closed.